package LeetCodeTask.BinarySearch;

/*一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。*/
/*eg 输入: [0,1,3]
        输出: 2*/

/**
 * 思路1 最笨遍历 （n-1），思路2 二分查找lg(n)
 * 二分查找思路，普遍二分查找对应二分界限，对给定值x，能判断x属于列表中的哪一半中
 */
public class LossNumSimple {

    public int missingNumber(int[] nums) {
        int i=0,j=nums.length-1;
        while (i<=j){//注意这里=不能少 否则会少考虑【0】 -》1的情况
            int m =(i+j)/2;
            if (m == nums[m]) {
                i = m+1;
            } else {
                j = m-1;
            }
        }
        return i;
    }

}
